#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<map>
#include<queue>
using namespace std;

class Solution {
public:
    int numSquares(int n) {
        int sq = sqrt(n), INF = 0x3f3f3f3f;
        vector<vector<int>> dp(sq + 1, vector<int>(n + 1));
        for (int i = 1; i <= n; ++i)
            dp[0][i] = INF;
        for (int i = 1; i <= sq; ++i)
        {
            for (int j = 0; j <= n; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= i * i)dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
            }
        }
        return dp[sq][n];
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        int l = strs.size();
        vector<vector<vector<int>>> dp(l + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
        for (int i = 1; i <= l; ++i)
        {
            int a = 0, b = 0;
            for (auto c : strs[i - 1])
            {
                c == '0' ? a += 1 : b += 1;
            }
            for (int j = 0; j <= m; ++j)
            {
                for (int k = 0; k <= n; ++k)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= a && k >= b)dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
                }
            }
        }
        return dp[l][m][n];
    }

    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        const int e = (int)1e9 + 7;
        int m = group.size();
        vector<vector<vector<int>>> dp(m + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
        dp[0][0][0] = 1;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 0; j <= n; ++j)
            {
                for (int k = 0; k <= minProfit; ++k)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= group[i - 1])dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[i][j][k] %= e;
                }
            }
        }
        int sum = 0;
        for (int j = 0; j <= n; ++j)
            sum = (sum + dp[m][j][minProfit]) % e;
        return sum;
    }

    struct cmp {
        bool operator()(const pair<int, int> m, const pair<int, int> n)
        {
            return m.second < n.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> hash;
        for (int num : nums)
            ++hash[num];
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> Q(hash.begin(), hash.end());
        vector<int> ret;
        while (k--)
        {
            ret.push_back(Q.top().first);
            Q.pop();
        }
        return ret;
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<int, vector<int>, greater<int>> Q;
        for (int i = 0; i < n; ++i)
        {
            Q.push(nums[i]);
            if (Q.size() > k)
                Q.pop();
        }
        return Q.top();
    }

    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 0; i <= n; ++i)
        {
            for (int j = 1; j <= i; ++j)
            {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<double> dp(target + 1);
        dp[0] = 1;
        for (int i = 0; i <= target; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (i >= nums[j]) dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};